The present invention is generally directed to computer systems. More particularly, the present invention is directed to an apparatus and a method for controlling the execution of machine instructions in a digital computer. Even more particularly, the present invention provides a mechanism for managing an instruction cache in a more efficient manner through the utilization of a queue structure resulting in fewer situations in which data is prematurely or unnecessarily removed from an instruction cache.
One of the major design goals in the construction of computer systems is the increase in computer speed. In order to achieve these speed objectives, several mechanisms have been introduced. In particular, computer system designers have employed cache memory structures which are relatively small but which are also relatively fast and which act, in essence, as a buffer between a main memory storage level and the storage level associated with machine registers. In order to take advantage of the speed characteristics of a cache memory, portions of the main memory are transferred to the cache memory from which they are executed. Since access to the cache is relatively rapid, the overall speed of the system is effectively increased. Additionally, while certain instructions are being executed out of one portion of cache memory it is possible to load other instructions into different portions of the cache memory which is usually organized into substructures referred to as "cache lines". However, it is nonetheless necessary to provide some mechanism for mapping main memory addresses into cache addresses. Accordingly, for this purpose, an N-entry directory is typically provided so as to allow reference to any one of N cache lines.
In addition to the utilization of cache memory structures for computer speed enhancement, it is also desirable to employ mechanisms for the recognition and prediction of computer instruction branching events. Known branch prediction mechanisms provide branch prediction and address information which in turn is used to determine the appropriate instruction sequence which is to be executed from a cache memory. In the present invention, branch prediction and branch history mechanisms play only an indirect role in the management of the cache structure in the present invention.
One of the trade-offs in the design of cache memory structures is that they are relatively small compared to main memory structures. Nonetheless, this size relationship provides a mechanism for increased cache speed. Accordingly, it is very desirable to provide a mechanism for loading a fixed number, K, of future instruction cache lines into a cache memory. These cache line entries are loaded well ahead of the times when they will be accessed and processed. However, the number of cache lines which can be preloaded is limited by the fact that there is a danger that one would overwrite a previously fetched cache line that either had not yet been processed or which might need to be reprocessed due to the presence of instruction loop conditions. The natural solution to this problem is the employment of larger cache structures. However, as the instruction cache size grows in terms of the number of cache lines, there is a concomitant and corresponding decline in cache speed. Accordingly, it is desirable to provide a mechanism for managing access to instructions within the instruction cache so as to reduce those instances in which a prefetched cache line is prematurely discarded.
In an ideal situation, when as many instructions as possible are being executed by the computing system from instruction sequences contained in the instruction cache itself, minimal reference is made to the slower main memory structure from which cache lines are replaced. Accordingly, it is seen that mechanisms for which cache lines are prematurely replaced experience speed penalties as a result. In particular, the use of an N-entry directory as a mechanism for associating a given instruction address to a particular cache line using a hashing or mapping function can in fact result in situations where subsequent cache lines overwrite previously fetched cache lines that had either not yet been processed or might need to be reprocessed. Accordingly, it is desirable to be able to provide a different and improved management system for instruction cache structures in digital computer systems.